﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution230
{

    Dictionary<TreeNode,int> map= new Dictionary<TreeNode,int>();//存每个节点的孩子数
    public int KthSmallest(TreeNode root, int k)
    {
        GetCount(root);//遍历一遍
        //找左边孩子的数量

        while (root!=null)
        {
          int count=  GetNodeCount(root.left);

            //if (map.ContainsKey(root))//root可能空，所以判断一下再赋值

            if (count ==k-1)//在左边
            {
                return root.val;
            }else if(count < k-1)
            {
                k = k - count-1;//减去左孩子的数量加根节点，在右边找第k大
                root= root.right;
            }
            else
            {
                root = root.left;
            }

        }

        return root.val;

    }

    private int GetNodeCount(TreeNode root)
    {
        if (root == null) return 0;

        if (map.ContainsKey(root))
        {
            return map[root];

        }
        else
        {
            Console.WriteLine("节点不在map里面");
            return 0;
        }
    }



    private int GetCount(TreeNode root)
    {

        if(root==null) return 0;

        int count= GetCount(root.left) + GetCount(root.right) + 1;   
        map.Add(root, count);


        return count;//这个时候左右孩子的值去map里面找

    }
}

class Program230
{
    static void Main230(string[] args)
    {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode();
        root.right = new TreeNode(2);
        Solution230
            solution = new Solution230();
       int res= solution.KthSmallest(root,2);
        Console.WriteLine(res);
    }
}